package kyssion.leetcode.num51_100;

public class code84_柱状图中最大的矩形 {
    public static void main(String[] args) {
        System.out.println(new code84_柱状图中最大的矩形().largestRectangleArea(
                new int[]{
                        2, 1, 5, 6, 2, 3
                }
        ));
    }

    /**
     * dp方法, 其实 这里有一个隐藏的条件
     * 其实这个有一个思路就是右界队列 通过这个队列当我 判断以x为位置结尾的数据的时候,我们只需要和右界队列比较,当右界小于x的时候,那么
     * 在x位置的前向矩阵就是本省
     * 如果右界大于x那就查找下一个右界, 这个右界队列还保证了 两个右界之间的数据一定是大于两个右界的
     * 通过这种方法来两次就能解决了
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        int[] h = new int[heights.length];
        int[] hLeft = new int[heights.length];
        int[] hRight = new int[heights.length];
        int hIndex = 0;
        for (int a = 0; a < heights.length; a++) {
            while (hIndex >= 0) {
                if (hIndex == 0) {
                    hLeft[a] = heights[a] * (a + 1);
                    break;
                } else if (heights[a] > heights[h[hIndex - 1]]) {
                    hLeft[a] = heights[a] * (a - h[hIndex - 1]);
                    break;
                } else {
                    hIndex--;
                }
            }
            h[hIndex] = a;
            hIndex++;
        }

        hIndex = 0;

        for (int a = heights.length - 1; a >= 0; a--) {
            while (hIndex >= 0) {
                if (hIndex == 0) {
                    hRight[a] = heights[a] * (heights.length - a);
                    break;
                } else if (heights[a] > heights[h[hIndex - 1]]) {
                    hRight[a] = heights[a] * (h[hIndex - 1] - a);
                    break;
                } else {
                    hIndex--;
                }
            }
            h[hIndex] = a;
            hIndex++;
        }
        int max = 0;
        for (int a = 0; a < heights.length; a++) {
            max = Math.max(max, hLeft[a] + hRight[a] - heights[a]);
        }
        return max;
    }

    /**
     * 扩展一下思路,其实有的时候使用递归来化简问题真的有用
     * 每次只要最小的数值就能解决问题了,复杂度 n*logn
     * @param heights
     * @return
     */
    public int largestRectangleArea2(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        return getMax(heights, 0, heights.length);
    }

    int getMax(int[] heights, int s, int e) {
        if (s >= e) return heights[s];
        int min = s;
        boolean sorted = true;
        for (int i = s; i < e; i++) {
            if (i > s && heights[i] < heights[i - 1]) sorted = false;
            if (heights[min] > heights[i]) min = i;
        }
        //这里可能优化了性能
        if (sorted) {
            int max = 0;
            for (int i = s; i < e; i++) {
                max = Math.max(max, heights[i] * (e - i));
            }
            return max;
        }
        int left = (min > s) ? getMax(heights, s, min) : 0;
        int right = (min < e - 1) ? getMax(heights, min + 1, e) : 0;
        return Math.max(Math.max(left, right), (e - s) * heights[min]);
    }
}
